package november.linkedlist.singleLinkedList;

import java.util.Stack;
import java.util.function.BiPredicate;

/**
 * @author huangxin
 * @date 2019/11/14-16:43
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList((curr, next) -> {
            return curr.id > next.id;
        });
 SingleLinkedList singleLinkedList2 = new SingleLinkedList((curr, next) -> {
            return curr.id > next.id;
        });

        singleLinkedList.addByBiPredicate(new Node(1, ""));
        singleLinkedList.addByBiPredicate(new Node(5, ""));
        singleLinkedList.addByBiPredicate(new Node(3, ""));
        singleLinkedList.addByBiPredicate(new Node(6, ""));
        singleLinkedList.addByBiPredicate(new Node(2, ""));
//        singleLinkedList.update(new Node(6, "更新的文本"));
//        singleLinkedList.delete(2);
//        System.out.println(singleLinkedList.count());
        singleLinkedList.show();
//        System.out.println("-----------------");
//        System.out.println(findLastIndexNode(singleLinkedList, 2));
        System.out.println("---------------");
//        reverse(singleLinkedList);
//        printReverse(singleLinkedList);



        singleLinkedList2.addByBiPredicate(new Node(9, ""));
        singleLinkedList2.addByBiPredicate(new Node(4, ""));
        singleLinkedList2.addByBiPredicate(new Node(10, ""));
        System.out.println(singleLinkedList2);
        System.out.println("---------------");

        SingleLinkedList singleLinkedList3 = new SingleLinkedList((curr, next) -> {
            return curr.id > next.id;
        });
        singleLinkedList3.head.next = mergeTwoLists(singleLinkedList.head.next,singleLinkedList2.head.next);

        System.out.println(singleLinkedList3);

    }

    public static Node findLastIndexNode(SingleLinkedList linkedList, int index) {
        //获取链表长度
        int count = linkedList.count();

        if (index > count || index <= 0) {
            System.out.println("越界");
            return null;
        }

        //假设5个元素,查找倒数第一个,5-1=4, 指针从第一个往后移4次,到达第5个(即倒数第一个)
        int eachNum = count - index;
        Node temp = linkedList.head.next;//指向第一个节点
        for (int i = 0; i < eachNum; i++) {
            temp = temp.next;
        }

        return temp;
    }

    public static void reverse(SingleLinkedList linkedList) {
        Node newHead = new Node(0, "");

        Node temp = linkedList.head.next;
        Node next;
        while (temp != null) {
            next = temp.next;

            temp.next = newHead.next;
            newHead.next = temp;

            temp = next;
        }

        linkedList.head = newHead;
    }

    public static void printReverse(SingleLinkedList linkedList) {
        if (linkedList.head.next == null) {
            System.out.println("链表为空");
            return;
        }

        Stack<Node> stack = new Stack<>();

        Node temp = linkedList.head.next;

        while (temp != null) {
            stack.add(temp);
            temp = temp.next;
        }

        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    public static Node mergeTwoLists(Node head1, Node head2) {
        if (head1 == null) {
            return head2;
        }

        if (head2 == null) {
            return head1;
        }

        Node head = null;
        if (head1.id > head2.id) {//head2小于head1
            head = head2;//head2在前面,当前节点指向head2
            head.next = mergeTwoLists(head1, head2.next);//当前节点的下个节点指向  head1和head2.next中小的那个
        } else {
            head = head1;
            head.next = mergeTwoLists(head1.next, head2);
        }
        return head;
    }


}


/**
 * 单向列表
 */
class SingleLinkedList {
    //jdk8自定义排序规则
    private BiPredicate<Node, Node> biPredicate;

    //头节点,不记录
    public Node head = new Node(0, "");

    public void add(Node node) {
        Node temp = head;

        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    public void delete(int id) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        Node temp = head;
        boolean flag = false;//是否找到
        //temp记录要删除的元素的前一个节点
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.id == id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //把temp.next的指针指向temp.next.next , 原来的temp.next(要删除的元素)则会自动回收
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到该节点");
        }
    }

    /**
     * 修改节点
     */
    public void update(Node update) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        Node temp = head.next;
        boolean flag = false;//是否找到
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.id == update.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = update.name;
        } else {
            System.out.println("没有找到该节点");
        }
    }


    public int count() {
        if (head.next == null) {
            return 0;
        }
        int count = 0;
        Node temp = head.next;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }


    /**
     * 根据排序规则插入
     *
     * @param node
     */
    public void addByBiPredicate(Node node) {
        //第一次插入
        if (head.next == null) {
            head.next = node;
            return;
        }
        Node temp = head;
        boolean flag = false;
        //链表不为空
        while (true) {
            if (temp.next == null) {
                break;
            }
            //根据传入的排序规则判断
            if (biPredicate.test(temp.next, node)) {
                break;
            }

            if (temp.next.id == node.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            System.out.println("插入的id重复");
            return;
        }
        node.next = temp.next;
        temp.next = node;
    }


    public SingleLinkedList() {
    }

    public SingleLinkedList(BiPredicate<Node, Node> biPredicate) {
        this.biPredicate = biPredicate;
    }


    //打印链表
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (isEmpty()) {
            sb.append("链表为空");
            return sb.toString();
        }
        //从头节点开始打印链表
        Node temp = head.next;
        do {
            sb.append(temp.toString());
            sb.append("\n");
            temp = temp.next;
        } while (temp != null);
        return sb.toString();
    }

    public void show() {
        System.out.println(this.toString());
    }

    private boolean isEmpty() {
        return this.head.next == null;
    }
}


class Node {
    public int id;
    public String name;
    public Node next;//指向下个节点


    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name=" + name +
                '}';
    }

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }
}
